package com.zklh.leetcode.interviewTop150;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * 从中序和后序遍历序列构造二叉树
 */
public class Solution106 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
    }

    private TreeNode buildTree(int[] inorder,int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
        if (inLeft == inRight) {
            return new TreeNode(inorder[inLeft]);
        }
        if (inLeft > inRight) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postRight]);
        int inMiddle = inLeft;
        while (inorder[inMiddle] != postorder[postRight]) {inMiddle++;}
        // buildLeft
        int leftLen = inMiddle - inLeft, rightLen = inRight - inMiddle;
        root.left = buildTree(inorder, inLeft, inMiddle-1, postorder, postLeft, postLeft+(leftLen-1));
        root.right = buildTree(inorder, inMiddle+1, inRight, postorder, postRight-rightLen, postRight-1);
        return root;
    }

    public static void main(String[] args) {
        Solution106 solution106 = new Solution106();
        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        System.out.println(solution106.buildTree(inorder, postorder));
    }
}
